package com.gqb.tree;

import java.util.ArrayList;
import java.util.List;

public class BinaryHuffmanTree {
	public static class Node {
		private int data;
		private String name;
		private Node leftNode;
		private Node rightNode;
		private Node parent;

		public Node(int data, Node parentNode) {
			super();
			this.data = data;
			this.parent = this.parent;
		}

		public Node(int data, String name) {
			super();
			this.data = data;
			this.name = name;
		}

		public Node() {
		}

		public String getName() {
			return name;
		}

		public void setName(String name) {
			this.name = name;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public Node getLeftNode() {
			return leftNode;
		}

		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}

		public Node getRightNode() {
			return rightNode;
		}

		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}

		public Node getParent() {
			return parent;
		}

		public void setParent(Node parent) {
			this.parent = parent;
		}
	}

	private Node rootNode;
	private int nodeCount;
	List<Node> nodes = new ArrayList<BinaryHuffmanTree.Node>();

	public boolean createTree(List<Node> treenodes) {
		if (null == rootNode) {
			Node min = getMinNode(treenodes);
			treenodes.remove(min);
			Node minSec = getMinNode(treenodes);
			treenodes.remove(minSec);
			rootNode = new Node(min.getData() + minSec.getData(), " ");
			rootNode.leftNode=min;
			rootNode.rightNode=minSec;
			min.parent = rootNode;
			minSec.parent = rootNode;
		}
		while (treenodes.size()>0) {
			Node min = getMinNode(treenodes);
			treenodes.remove(min);
			Node node = new Node(rootNode.getData() + min.getData(), "");
			node.leftNode=min;
			node.rightNode=rootNode;
			min.parent = node;
			rootNode.parent = node;
			rootNode = node;

		}
		return true;
	}

	public Node getMinNode(List<Node> treeNodes) {
		for (int i = 0; i < treeNodes.size(); i++) {
			for (int j = i + 1; j < treeNodes.size(); j++) {
				Node temp = new Node();
				if (treeNodes.get(i).getData() < treeNodes.get(j).getData()) {
					temp = treeNodes.get(i);
					treeNodes.set(i, treeNodes.get(j));
					treeNodes.set(j, temp);
				}
			}
		}
		return treeNodes.get(treeNodes.size() - 1);
	}
	public void breadthFirst(){
		List<Node> list=new ArrayList<>();
		list.add(rootNode);
		while(list.size()>0){
			Node node=list.remove(0);
			if(node.leftNode!=null)
				list.add(node.leftNode);
			if(node.rightNode!=null)
				list.add(node.rightNode);
			System.out.print(node.getData()+"-");
		}
	}

	public static void main(String[] args) {
		BinaryHuffmanTree binaryHuffmanTree = new BinaryHuffmanTree();
		List<Node> nodes = new ArrayList<>();
		nodes.add(new Node(40, "A"));
		nodes.add(new Node(8, "B"));
		nodes.add(new Node(10, "C"));
		nodes.add(new Node(30, "D"));
		nodes.add(new Node(12, "E"));
		nodes.add(new Node(2, "F"));
		binaryHuffmanTree.createTree(nodes);
		binaryHuffmanTree.breadthFirst();
	}
}
